Markov Chain

A special kind of stochastic process.

Definition

$$ \begin{aligned} P[X_{n+1} = x_{n+1} | X_{n} = x_{n}, \ldots, X_{1} = x_1] &= P[X_{n+1} = x_{n+1} | X_{n} = x_{n}] \\ \forall x^{n+1} \in \mathcal{X}^{n+1} \end{aligned} $$

Property

Time-Invariance

$$ \begin{aligned} P[X_{n + 1} = b | X_{n} = a] &= P[X_{2} = b | X_{1} = a] \\ \forall a, b &\in \mathcal{X}, \forall n \end{aligned} $$

Matrix Representation

The pmf can be compressed into matrix form:

$$ \begin{aligned} P_{i, j} = P[X_{n+1} = j | X_{n} = i] \end{aligned} $$

i.e.:

$$ \begin{aligned} P &= \begin{bmatrix} 1 - \alpha & \alpha & 0 \\ \beta & 1 - \alpha - \beta & \alpha \\ 0 & \beta & 1 - \beta \end{bmatrix} \end{aligned} $$
The vector of probabilities at time $n$, $X_n$:

$$ \begin{aligned} \mu_n &= \begin{bmatrix} P[X_n = 1] \\ \cdots \\ P[X_n = M] \end{bmatrix} \end{aligned} $$

Update:

$$ \begin{aligned} \mu_{n + 1} &= \mu_n \cdot P \end{aligned} $$

Stationary Distribution

A distribution $\mu$ is a stationary if: $$ \begin{aligned} \mu = \mu \cdot P \end{aligned} $$

Specification

Everything needed to specify a time-invariant Markov Chain:

(All Possible States: $\mathcal{X}$)
State Transition Matrix: $P \in \mathbb{R}^{|\mathcal{X}| \times |\mathcal{X}|}$
Starting Distribution: $\mu_1$

Theorems

A irreducible, aperiodic Markov Chain has a unique stationary distribution, called limiting distribution:

$$ \begin{aligned} \mu &= \left( \lim_{n \rightarrow \infty} P_{ij}^{n} \right) \cdot \mu_0, &\forall \mu_0 \\ \end{aligned} $$

If $\{X_i\}$ is a stationary time-invariant Markov process, then:

$$ \begin{aligned} H(\mathcal{X}) &= H(X_2 | X_1) \end{aligned} $$